package Aleehot100;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * ClassName: c074
 * Package: Aleehot100
 * Description:215. 数组中的第K个最大元素
 *
 * @Author BCXJ
 * @Create 2025/8/26 08:37
 * @Version 1.0
 * @Since 1.0
 */
public class c074 {
    /*
        public int findKthLargest(int[] nums, int k) {
        //return violence(nums, k);
        return findKthLargest2(nums, k);
    }

    public static int[] randomGenerateArr(int size, int length) {
        int[] ints = new int[length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = (int) (Math.random() * size);
        }
        return ints;
    }

    public static int violence(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public static int findKthLargest2(int[] nums, int k) {
        return process(nums, nums.length - k, 0, nums.length - 1);
    }

    private static int process(int[] nums, int k, int l, int r) {
        int randomIndex;
        while (l <= r) {
            randomIndex = l + (int) (Math.random() * (r - l + 1)); // l ... r
            int[] res = partitionForThree(nums, l, r, randomIndex);
            if (k < res[0] + 1) {
                r = res[0];
            } else if (k > res[1] - 1) {
                l = res[1];
            } else {
                return nums[k];
            }
        }
        return -1;
    }

    /**
     * 三区划分
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
//    private static int[] partitionForThree(int[] arr, int l, int r, int index) {
//        int ml = l;
//        int mr = r;
//        int num = arr[index];
//        int i = l;
//        while (i <= mr) {
//            if (arr[i] < num) {
//                swap(arr, ml++, i++);
//            } else if (arr[i] == num) {
//                i++;
//            } else if (arr[i] > num) {
//                swap(arr, mr--, i);
//            }
//        }
//        return new int[] { ml - 1, mr + 1 };
//    }



    public static void main(String[] args) {
        int[] arr = {3,2,1,5,6,4};
        System.out.println(findKthLargest(arr, 2));
        System.out.println(Arrays.toString(arr));
        System.out.println(123 + "qsd");
    }

    public static int findKthLargest(int[] nums, int k) {
        //return violence(nums, k);
        return findKthLargest2(nums, k);
    }

    private static int findKthLargest2(int[] nums, int k) {
        return Quickselect(nums, nums.length - k, 0, nums.length - 1);
    }

    /**
     * 快排解法
     * @param nums
     * @param k 第k个
     * @param l 做边界
     * @param r 右边界
     * @return
     */
    private static int Quickselect(int[] nums, int k, int l, int r) {
        while(l <= r) {
            int index = (int)(Math.random() * (r - l + 1)) + l; // 随机下标
            int num = nums[index];
            int[] indexRes = partitionForThree(nums, num, l, r);
            if(indexRes[0] + 1 > k) {
                r = indexRes[0];
            } else if(indexRes[1] - 1 < k) {
                l = indexRes[1];
            } else {
                return num;
            }
        }
        return -1;
    }

    /**
     * 三区划分(荷兰国旗问题)
     * @param arr
     * @param num
     * @param l
     * @param r
     * @return
     */
    private static int[] partitionForThree(int[] arr, int num, int l, int r) {
        int midL = l - 1;
        int midR = r + 1, i = l;
        while(i < midR) {
            // 等于
            if(arr[i] == num) {
                i ++;
            }
            // 小于
            else if(arr[i] < num) {
                swap(arr, ++midL, i ++);
            }
            // 大于
            else if(arr[i] > num) {
                swap(arr, --midR, i);
            }
        }
        return new int[]{midL, midR};
    }
    private static void swap(int[] arr, int m, int i) {
        int temp = arr[m];
        arr[m] = arr[i];
        arr[i] = temp;
    }



}
